package com.gitee.wsl.collections.iterator

import com.gitee.wsl.base.Objects
import com.gitee.wsl.ext.base.Arrays.fill


/**
 * This iterator creates permutations of an input collection, using the
 * Steinhaus-Johnson-Trotter algorithm (also called plain changes).
 *
 *
 * The iterator will return exactly n! permutations of the input collection.
 * The `remove()` operation is not supported, and will throw an
 * `UnsupportedOperationException`.
 *
 *
 *
 * NOTE: in case an empty collection is provided, the iterator will
 * return exactly one empty list as result, as 0! = 1.
 *
 *
 * @param <E>  the type of the objects being permuted
 * @since 4.0
</E> */
class PermutationIterator<E>(collection: Collection<E>) : Iterator<List<E>> {
    /**
     * Permutation is done on these keys to handle equal objects.
     */
    private val keys: IntArray = IntArray(collection.size)

    /**
     * Mapping between keys and objects.
     */
    private val objectMap: Map<Int, E>

    /**
     * Direction table used in the algorithm:
     *
     *  * false is left
     *  * true is right
     *
     */
    private val direction: BooleanArray = BooleanArray(collection.size)

    /**
     * Next permutation to return. When a permutation is requested
     * this instance is provided and the next one is computed.
     */
    private var nextPermutation: List<E>?

    /**
     * Standard constructor for this class.
     * @param collection  the collection to generate permutations for
     * @throws NullPointerException if coll is null
     */
    init {
        fill(direction, false)
        var value = 1
        objectMap = HashMap()
        for (e in collection) {
            objectMap.put(value, e)
            keys[value - 1] = value
            value++
        }
        nextPermutation = ArrayList(collection)
    }

    /**
     * Indicates if there are more permutation available.
     * @return true if there are more permutations, otherwise false
     */
     override fun hasNext(): Boolean {
        return nextPermutation != null
    }

    /**
     * Returns the next permutation of the input collection.
     * @return a list of the permutator's elements representing a permutation
     * @throws NoSuchElementException if there are no more permutations
     */
     override fun next(): List<E> {
        if (!hasNext()) {
            throw NoSuchElementException()
        }

        // find the largest mobile integer k
        var indexOfLargestMobileInteger = -1
        var largestKey = -1
        for (i in keys.indices) {
            if (direction[i] && i < keys.size - 1 && keys[i] > keys[i + 1] ||
                !direction[i] && i > 0 && keys[i] > keys[i - 1]
            ) {
                if (keys[i] > largestKey) { // NOPMD
                    largestKey = keys[i]
                    indexOfLargestMobileInteger = i
                }
            }
        }
        if (largestKey == -1) {
            val toReturn = nextPermutation
            nextPermutation = null
            return toReturn!!
        }

        // swap k and the adjacent integer it is looking at
        val offset = if (direction[indexOfLargestMobileInteger]) 1 else -1
        val tmpKey = keys[indexOfLargestMobileInteger]
        keys[indexOfLargestMobileInteger] = keys[indexOfLargestMobileInteger + offset]
        keys[indexOfLargestMobileInteger + offset] = tmpKey
        val tmpDirection = direction[indexOfLargestMobileInteger]
        direction[indexOfLargestMobileInteger] = direction[indexOfLargestMobileInteger + offset]
        direction[indexOfLargestMobileInteger + offset] = tmpDirection

        // reverse the direction of all integers larger than k and build the result
        val nextP = ArrayList<E>()
        for (i in keys.indices) {
            if (keys[i] > largestKey) {
                direction[i] = !direction[i]
            }
            nextP.add(objectMap[keys[i]]!!)
        }
        val result = nextPermutation
        nextPermutation = nextP
        return result!!
    }

}
